﻿/*
* 可变分区管理方式下采用首次适应算法实现主存分配和回收
* Yu Sitong
* YuSitong1999@qq.com
* 2019-09-27
*/

#include <iostream>
#include <vector>
using namespace std;

// 内存段
struct Partition
{
	int id;
	int beginPosition;
	int length;
	Partition(int id = 1,int beginPosition = 0,int length = 128) :
		id(id), beginPosition(beginPosition), length(length) {}
};

// 空闲区说明表
vector<Partition> list;
// 已分配内存表
vector<Partition> task;
int tot;

// 分配指定大小连续内存
void allocate(int space)
{
	int index = 0;
	bool exist = false;
	while (index != static_cast<int>(list.size()))
	{
		if (list[index].length >= space)
		{
			cout << "分配成功\n起点 : " << list[index].beginPosition << "\n长度 : " << space << "\n";
			cout << "编号 : " << tot << endl << endl;
			task.push_back(Partition(tot, list[index].beginPosition, space));
			++tot;
			exist = true;
			list[index].length -= space;
			list[index].beginPosition += space;
			break;
		}
		++index;
	}
	if (!exist)
	{
		cout << "无剩余连续空间！\n\n";
	}
}

// 释放指定点开始的指定长度内存
void rel(int beginPosition, int length)
{
	int index = static_cast<int>(list.size());
	while (index != 0)
	{
		if (list[index - 1].beginPosition < beginPosition)
		{
			list.insert(list.begin() + index, Partition(0, beginPosition, length));
			return;
		}
		--index;
	}
	list.insert(list.begin(), Partition(0, beginPosition, length));
}

// 更新空闲区说明表信息
void update()
{
	int index = 0;
	while (index != static_cast<int>(list.size()))
	{
		if (list[index].length == 0)
		{
			list.erase(list.begin() + index);
			continue;
		}
		if (index + 1 != static_cast<int>(list.size()) &&
			list[index].beginPosition+list[index].length == list[index+1].beginPosition)
		{
			list[index].length += list[index + 1].length;
			list.erase(list.begin() + index + 1);
			continue;
		}
		list[index].id = index + 1;
		++index;
	}
}

// 显示空闲区说明表信息
void display()
{
	for (const auto& partition : list)
		cout << partition.id << " : " << partition.beginPosition << " + " << partition.length << endl;
	cout << endl << endl;
}

int main()
{
	// 开始内存全为空
	list.push_back(Partition());

	while (true)
	{
		cout << "1 - 申请 0 - 释放" << endl;
		int operation;
		cin >> operation;
		if (operation)
		{
			// 申请指定大小连续内存 并获取内存块编号
			int space;
			cin >> space;
			allocate(space);
			update();
		}
		else
		{
			// 释放指定编号内存块
			int taskId;
			cin >> taskId;
			if (taskId >= static_cast<int>(task.size()))
			{
				cout << "编号不存在!" << endl;
			}
			else if (task[taskId].id == -1)
			{
				cout << "空间重复回收!" << endl;
			}
			else
			{
				rel(task[taskId].beginPosition, task[taskId].length);
				update();
				task[taskId].id = -1;
			}
		}
		display();
	}
	return 0;
}